package top.pro51.guide.chapter1;

import java.util.Stack;

/**
 * @ClassName 用一个栈实现另一个栈的排序
 * @Description:
 * @Author: WangWenpeng
 * @date: 12:03 2021/1/11
 * @Version 1.0
 */
public class 用一个栈实现另一个栈的排序 {

    /**
     * 待排序的栈stack， 辅助栈help。 在stack上执行pop操作，记元素为cur
     * if cur <= 【help 的栈顶元素】，cur 压入help栈中；
     * else cur > 【help 的栈顶元素】，逐一弹出help， 直到cur <= 【help 的栈顶元素】，在将cur压入help
     * 一直执行以上操作，直到stack中的全部元素都导入help栈中，（此时从栈顶到栈底：有小到大），最后，将help栈中的元素，pop一下，排序
     * @param stack
     */
    public static void sortStackByStack(Stack<Integer> stack) {
        Stack<Integer> help = new Stack<Integer>();
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            while (!help.isEmpty() && help.peek() > cur) {
                stack.push(help.pop());
            }
            help.push(cur);
        }
        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(3);
        stack.push(1);
        stack.push(6);
        stack.push(2);
        stack.push(5);
        stack.push(4);
        sortStackByStack(stack);
        int stack_size = stack.size();
        System.out.println("stack元素是：");
        for (int size = 0; size < stack_size; size++) {
            System.out.println(stack.pop());
        }
    }
}
